package 数据结构专栏.A_二叉树专栏.C_对称问题;

import 数据结构专栏.A_二叉树专栏.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Title
 * @Author zhengqiang.tan
 * @Date 2021/6/20 4:21 PM
 */
public class 反转二叉树 {

    /**
     * 递归版本
     *
     * @param node
     * @return
     */
    public TreeNode invertTree(TreeNode node) {
        if (node == null) return null;

        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        invertTree(node.left);
        invertTree(node.right);
        return node;
    }

    /**
     * 队列实现
     * @param root
     * @return
     */
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();// 移除并返问队列头部的元素
            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }

}


//值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
//        　　add         增加一个元索                          如果队列已满，则抛出一个IIIegaISlabEepeplian异常
//        　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
//        　　element  返回队列头部的元素               如果队列为空，则抛出一个NoSuchElementException异常
//        　　offer        添加一个元素并返回true        如果队列已满，则返回false
//        　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
//        　　peek       返回队列头部的元素               如果队列为空，则返回null
//        　　put          添加一个元素                          如果队列满，则阻塞
//        　　take        移除并返回队列头部的元素    如果队列为空，则阻塞